package 前缀树的相关题目;

import java.util.HashSet;

// 数组中两个数的最大异或值
// 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n
// 1 <= nums.length <= 2 * 10^5
// 0 <= nums[i] <= 2^31 - 1
// 测试链接 : https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
public class Code02_TwoNumbersMaximumXor {

    // 前缀树的做法
    // 好想
    public static int findMaximumXOR(int[] nums) {
        // 为每个数创建前缀树
        build(nums);
        int ans = 0;
        for (int num : nums) {
            ans = Math.max(ans, maxXor(num));
        }
        clear();
        return ans;
    }

    // 前缀树使用了多少空间
    public static int cnt;

    // 准备这么多静态空间就够了，实验出来的
    // 如果测试数据升级了规模，就改大这个值
    public static int MAXN = 3000001;

    public static int[][] tree = new int[MAXN][2];

    // 数字只需要从哪一位开始考虑
    public static int high;
    public static void build(int[] nums){
        cnt = 1;
        // 找个最大值，这样就不必为每个数都创建前缀树32个节点，节省空间
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        // 计算数组最大值的二进制状态，有多少个前缀的0
        // 可以忽略这些前置的0，从high位开始考虑
        high = 31 - Integer.numberOfLeadingZeros(max);

        for (int num : nums) {
            insert(num);
        }
    }

    public static void insert(int num){
        int cur = 1;
        for(int i = high, path; i >= 0; i--){
            // 从第high位开始，向右移动i位则到第0为，与上1，则得这一位的数是0或1
            path = (num >> i) & 1;
            if(tree[cur][path] == 0){
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
    }

    public static int maxXor(int num){
        // 前缀树目前来到的节点编号
        int cur = 1;
        // 最终异或的结果(尽量大)
        int ans = 0;
        for(int i = high, status, want; i >= 0; i--){
            // status : num第i位的状态
            status = (num >> i) & 1;
            // want : num第i位希望遇到的状态
            want = status ^ 1;
            // 询问前缀树，能不能达成
            if(tree[cur][want] == 0){
                // 不能达成
                want ^= 1;
            }
            // want变成真的往下走的路
            ans |= (status ^ want) << i;
            cur = tree[cur][want];
        }
        return ans;
    }

    public static void clear(){
        for(int i = 1; i <= cnt; i++){
            tree[i][0] = tree[i][1] = 0;
        }
    }


    // 用哈希表的做法
    // 难想!!!
    public static int findMaximumXOR2(int[] nums){
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        // ans代表 : 31....i+1 已经达成的目标
        int ans = 0;
        HashSet<Integer> set = new HashSet<>();
        for(int i = 31 - Integer.numberOfLeadingZeros(max); i >= 0; i--){
            // 在ans基础上希望得到更好的结果
            int better = ans | (1 << i);
            set.clear();
            for (int num : nums) {
                // num : 31.....i 这些状态保留，剩下全成0
                num = (num >> i) << i;
                set.add(num);
                // num ^ 某状态 是否能 达成better目标，就在set中找 某状态 : better ^ num
                if(set.contains(better ^ num)){
                    // 目标达成，则更新ans，考虑下一位
                    ans = better;
                    break;
                }
            }
        }
        return ans;
    }
}
